package LinkedList.Medium;

import DataStructures.ListNode;

public class LC0142 {
    /**
     * 检测链表是否成环，并返回环的入口。
     * 这里实现了Krahets@LeetCode的解法。
     * 寻找链表中结点的题目，如寻找距离尾部第K个结点，寻找环入口，寻找公共尾部入口等问题，常用双指针法解决。
     * 检测链表是否存在环，这个问题的解法是套路化的，即利用快慢指针，如果指针在某个时候相遇，那么便存在环。
     * 本题的难点在于，如何确定环的入口。
     * 由于本题要求返回入口结点的指针，因此考虑【在满足某种情况时，将某个指针指向的结点返回】。其中，返回双指针相遇时指向的结点，就是一种可以尝试的思路。
     * 考虑快慢指针相遇时，两个指针经过的结点数。为了简化分析，我们只考虑快指针步进两步后与慢指针重合的情形。
     * 记环上结点数为r，环外结点数为o；相遇时，快指针经过结点数为f，慢指针经过结点数为s；那么有f=2s，且f-s=kr => s=kr，其中k∈N+。
     * 考虑什么情况下，双指针能同时指向入口结点。当s=o+1+nr时（n∈N），慢指针指向入口结点。
     * 在快慢指针初次相遇时，慢指针位置为kr。只需再走过o+1个结点，即可再次指向入口结点。
     * 但是o是未知的。联系到我们想要返回的是双指针重合时指向的结点，一种自然的想法就是令另外一个指针（重用f）从链表头开始前进，每次前进一步。
     * 这样当双指针重合时，f经过了o+1步，s经过了kr+o+1步，恰好指向了环的入口。
     * 这道题目有2个值得学习的思想：
     * 1. 简化问题。快指针追上慢指针可能有2种情况，即快指针从当前位置步进1步时追上慢指针，也有可能是步进2步时追上慢指针。分类讨论可能使问题的分析和编码都变得复杂。因此，这里只考虑了快指针步进2步后与慢指针重合的情形。这可能并不会显著增加算法的复杂度（**这一点待证明，但是在碰到问题时，建议直接用这一策略**）。
     * 2. 当需要返回链表中符合某种性质的结点时，首先考虑将某种情况下，某指针指向的结点返回。
     * 例如，就本题而言，相比尝试从方程中解出入口结点的位置，从快慢指针重合的角度来思考问题，可能能更快得到解法。
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head.next;
        if (fast == null) return null;
        if (slow == fast) return head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
            if (fast == null) return null;
            fast = fast.next;
            if (fast == null) return null;
        } // 退出循环时，双指针第一次相遇

        fast = head;
        slow = slow.next;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(new int[]{3, 2, 0, -4});
        head.next.next.next.next = head.next;
        detectCycle(head);
    }
}
